/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2020年12月19日
*   描    述：
*   Copyright (C) 2020 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    int minimumDeleteSum(string s1, string s2) {
        int str1 = s1.size();
        int str2 = s2.size();
        vector<vector<int>>dp(str1 + 1, vector<int>(str2 + 1, 0));
        for(int i = str1-1; i >= 0; i--){
            dp[i][str2] = s1[i] + dp[i+1][str2];
        }
        for(int j = str2-1; j >= 0; j--){
            dp[str1][j] = s2[j] + dp[str1][j+1];
        }

        for(int i = str1 - 1; i >= 0; i--){
            for(int j = str2 - 1; j >= 0; j--){
                if(s1[i] == s2[j]){
                    dp[i][j] = dp[i+1][j+1];
                } else {
                    dp[i][j] = min(dp[i+1][j] + s1[i], dp[i][j+1] + s2[j]);
                }
            }
        }

        return dp[0][0];
    }
};
